﻿#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <fstream>
#include <cassert>
using namespace std;
template<class T,class P>

class TreeNode
{
public:
	TreeNode(T _key,P * pdata = NULL)
	{
		key = _key;
		sateliteData = pdata;
		parentNode = rightNode = leftNode = NULL;
	}
	T key;
	P * sateliteData;
	TreeNode * leftNode;
	TreeNode * rightNode;
	TreeNode * parentNode;
};
template<class T,class P>
class BinaryTree
{
public:
	BinaryTree()
	{
		root = NULL;
	}
	TreeNode<T,P> * root;
	void Inorder_Walk(ofstream &fout);
	void Inorder_Walk(TreeNode<T,P>* node,ofstream & fout);
	void Preorder_Walk(ofstream &fout);//前序
	void Preorder_Walk(TreeNode<T,P>* node,ofstream & fout,int level);

	TreeNode<T,P> * Search(T key);
	TreeNode<T,P> * Search(TreeNode<T,P>* node,T key);

	TreeNode<T,P> * Iterative_Search(T key);
	TreeNode<T,P> * Iterative_Search(TreeNode<T,P>* node,T key);
	TreeNode<T,P>* Min(TreeNode<T,P>* node);
	TreeNode<T,P>* Min();
	TreeNode<T,P>* Max(TreeNode<T,P>* node);
	TreeNode<T,P>* Max();
	TreeNode<T,P>* TreeSuccessor(TreeNode<T,P>* node);

	TreeNode<T,P>*  Insert(TreeNode<T,P>* z);
	TreeNode<T,P>* Delete(TreeNode<T,P>* z,TreeNode<T,P>*& x,TreeNode<T,P>*& p);
	void LeftRotate(TreeNode<T,P>* x);
	void RightRotate(TreeNode<T,P>* y);

	bool IsSorted(); //是二叉搜索树吗
	bool IsSorted(TreeNode<T,P>* node,T& minVal,T& maxVal); //是二叉搜索树吗

};

template<class T,class P>
bool BinaryTree<T,P>::IsSorted()
{
	if (root == NULL)
	{
		return true;
	}
	T minV,maxV;
	return IsSorted(root,minV,maxV);

}
template<class T,class P>
bool BinaryTree<T,P>::IsSorted(TreeNode<T,P>* node,T& minV,T&maxV)
{
	T lminV,lmaxV;
	T rminV,rmaxV;

	if (node->leftNode!=NULL)
	{
		bool res = IsSorted(node->leftNode,lminV,lmaxV);
		if (!res)
		{
			return false;
		}
	}
	if (node->rightNode!=NULL)
	{
		bool res = IsSorted(node->rightNode,rminV,rmaxV);
		if (!res)
		{
			return false;
		}
	}
	if (node->leftNode!=NULL)
	{
		if (lmaxV>node->key)
		{
			return false;
		}
	}
	if (node->rightNode!=NULL)
	{
		if (rminV < node->key)
		{
			return false;
		}
	}

	if (node->leftNode == NULL)
	{
		minV = node->key;
	}else{
		minV = lminV;
	}

	if (node->rightNode == NULL)
	{
		maxV = node->key;
	}else{
		maxV = rmaxV;
	}
	return true;
}

template<class T,class P>
void BinaryTree<T,P>::Preorder_Walk(ofstream &fout)
{
	if (root == NULL)
	{
		fout << "empty tree"<<endl;
	}
	Preorder_Walk(root,fout,0);
	fout << (IsSorted()?"sorted":"unsorted") << endl;

}

template<class T,class P>
void BinaryTree<T,P>::Preorder_Walk(TreeNode<T,P>* node,ofstream & fout,int level)
{
	if (node == NULL)
	{
		return;
	}
	for (int i = 0;i<level;i++)
	{
		fout << "\t";
	}
	if (node->parentNode!=NULL && node->parentNode->leftNode == node)
	{
		fout << "L:";
	}
	if (node->parentNode!=NULL && node->parentNode->rightNode == node)
	{
		fout << "R:";
	}

	fout << node->key << endl;
	Preorder_Walk(node->leftNode,fout,level + 1);
	Preorder_Walk(node->rightNode,fout,level + 1);
}

template<class T,class P>
void BinaryTree<T,P>::LeftRotate(TreeNode<T,P>* x)
{
	assert(x != NULL);
	assert(x->rightNode !=NULL);

	TreeNode<T,P>* y = x->rightNode;
	TreeNode<T,P>* p = x->parentNode;

	x->rightNode = y->leftNode;
	if (x->rightNode)
	{
		x->rightNode->parentNode = x;
	}

	y->parentNode = p;

	if (p)
	{
		if (x == p->leftNode)
			p->leftNode = y;
		else
			p->rightNode = y;
	}else{
		root = y;
	}

	x->parentNode = y;
	y->leftNode = x;
}
template<class T,class P>
void BinaryTree<T,P>::RightRotate(TreeNode<T,P>* y)
{
	assert(y != NULL);
	assert(y->leftNode !=NULL);

	TreeNode<T,P>* x = y->leftNode;
	TreeNode<T,P>* p = y->parentNode;

	y->leftNode = x->rightNode;
	if (y->leftNode)
	{
		y->leftNode->parentNode = y;
	}

	x->parentNode = p;

	if (p)
	{
		if (y == p->leftNode)
			p->leftNode = x;
		else
			p->rightNode = x;
	}else{
		root = x;
	}

	y->parentNode = x;
	x->rightNode = y;
}


//返回x为被删节点的孩子,p为被删节点的父亲(两者都可能为空)
template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Delete(TreeNode<T,P>* z,TreeNode<T,P>*& x,TreeNode<T,P>*& p)
{
	if (z == NULL)
	{
		x = p = NULL;
		return NULL;
	}

	TreeNode<T,P>* y;
	if (z->leftNode == NULL || z->rightNode == NULL)
	{
		y = z;
	}else
	{
		y = TreeSuccessor(z);
	}

	//////////////////////////////////////////////////////////////////////////
	//y 最多只有一个孩子

	if (y->leftNode!=NULL)
	{
		x = y->leftNode;
	}else{
		x = y->rightNode;
	}

	//如果x为空，则y没有孩子
	p = y->parentNode;
	if (x != NULL)
	{
		x->parentNode = p;
	}
	if (p == NULL)
	{
		root = x;
	}else{
		if (y == p->leftNode)
			p->leftNode = x;
		else
			p->rightNode = x;
	}

	if (y!=z)
	{
		z->key = y->key;
		z->sateliteData = y->sateliteData;
	}
	return y;
}


//返回插入节点的父节点
template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Insert(TreeNode<T,P>* z)
{
	TreeNode<T,P>* y = NULL;
	TreeNode<T,P>* x = root;
	while (x != NULL)
	{
		y = x;
		if (z->key < x->key)
		{
			x = x->leftNode;
		}else{
			x = x->rightNode;
		}
	}
	z->parentNode = y;
	if (y == NULL)
	{
		root = z;
	}else{
		if (z->key < y->key)
		{
			y->leftNode = z;
		}else
		{
			y->rightNode = z;
		}
	}
	return y;
}
template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::TreeSuccessor(TreeNode<T,P>* node)
{
	if (node == NULL)
	{
		return NULL;
	}
	if (node->rightNode!=NULL)
	{
		return Min(node->rightNode);
	}
	TreeNode<T,P>* y = node->parentNode;
	while (y!=NULL && y->rightNode==node)  //node是y的右孩子
	{
		node = y;
		y = node->parentNode;
	}
	return y;
}

template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Max()
{
	return Max(root);
}

template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Max(TreeNode<T,P>* node)
{
	if (node == NULL)
	{
		return NULL;
	}
	if (node->rightNode!=NULL)
	{
		 node = node->rightNode;
	}
	return node;
}

template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Min()
{
	return Min(root);
}

template<class T,class P>
TreeNode<T,P>* BinaryTree<T,P>::Min(TreeNode<T,P>* node)
{
	if (node == NULL)
	{
		return NULL;
	}
	if (node->leftNode!=NULL)
	{
		node = node->leftNode;
	}
	return node;
}

template<class T,class P>
void BinaryTree<T,P>::Inorder_Walk(ofstream & fout)
{
	Inorder_Walk(root,fout);
}

template<class T,class P>
void BinaryTree<T,P>::Inorder_Walk(TreeNode<T,P>* node,ofstream & fout)
{
	if (node != NULL)
	{
		Inorder_Walk(node->leftNode,fout);
		fout << node->key << endl;
		Inorder_Walk(node->rightNode,fout);
	}
}

template<class T,class P>
TreeNode<T,P> * BinaryTree<T,P>::Search(T key)
{
	return Search(root,key);
}
template<class T,class P>
TreeNode<T,P> * BinaryTree<T,P>::Search(TreeNode<T,P>* node,T key)
{
	if (node == NULL || node->key == key)
	{
		return node;
	}
	if (key < node->key)
	{
		return Search(node->leftNode,key);
	}
	return Search(node->rightNode,key);
}

template<class T,class P>
TreeNode<T,P> * BinaryTree<T,P>::Iterative_Search(T key)
{
	return Iterative_Search(root,key);
}
template<class T,class P>
TreeNode<T,P> * BinaryTree<T,P>::Iterative_Search(TreeNode<T,P>* node,T key)
{
	while (node != NULL && node->key!=key)
	{
		if (key < node->key)
		{
			node = node->leftNode;
		}else
		{
			node = node->rightNode;
		}
	}
	return node;
}

#endif